Đâu là con đường ngắn nhất để đi từ Rotterdam đến Groningen, hay nói chung: từ thành phố này đến thành phố nhất định. Đây là thuật toán tìm đường đi ngắn nhất, mà tôi đã thiết kế trong khoảng hai mươi phút. Vào một buổi sáng đi mua sắm ở Amsterdam cùng vị hôn thê trẻ tuổi với sự mệt mỏi, chúng tôi ngồi trên sân thượng để uống một tách cà phê và tôi chỉ nghĩ liệu tôi có thể làm điều này không, và sau đó tôi đã thiết kế thuật toán tìm đường đi ngắn nhất. Như tôi đã nói, đó là một phát minh trong hai mươi phút. Trên thực tế, nó đã được xuất bản vào năm 1959, ba năm sau đó. Các ấn phẩm vẫn có thể đọc được, quả thật như vậy, và khá đẹp. Một trong những lý do khiến nó rất hay là tôi đã thiết kế nó mà không cần bút chì và giấy. Sau này tôi đã học được rằng một trong những lợi thế của việc thiết kế mà không cần bút chì và giấy là bạn gần như buộc phải tránh đi mọi sự phức tạp có thể tránh được. Cuối cùng, thuật toán đó đã trở thành một trong những nền tảng giúp tôi nổi tiếng, với sự kinh ngạc lớn của tôi.—Edsger Dijkstra trong một cuộc phỏng vấn với Philip L. Frana, Communications of the ACM, 2001[1].

Dijkstra đã nghĩ về bài toán đường đi ngắn nhất khi làm việc tại Trung tâm Toán học ở Amsterdam năm 1956 với tư cách là một lập trình viên để chứng minh khả năng của một máy tính mới có tên ARMAC[2]. Mục tiêu của ông là chọn cả một bài toán và giải pháp (sẽ được tạo bởi máy tính) mà những người không thuần tính toán vẫn có thể hiểu được. Ông đã thiết kế thuật toán đường đi ngắn nhất và sau đó triển khai nó cho ARMAC bằng bản đồ giao thông được đơn giản hóa một chút của 64 thành phố ở Hà Lan[3]. Một năm sau, ông gặp một vấn đề khác từ các kỹ sư phần cứng làm việc trên máy tính tiếp theo của học viện: giảm thiểu lượng dây cần thiết để kết nối các chân trên bảng điều khiển phía sau của máy. Như một giải pháp, ông đã phát hiện lại thuật toán Prim (được biết đến trước đó với Jarník, và cũng được Prim khám phá lại). Dijkstra đã xuất bản thuật toán vào năm 1959, 2 năm sau Prim và 29 năm sau Jarník.[4][5]